package com.leetcode.stack_queue;

import java.util.Stack;

/**
 * @author Dennis Li
 * @date 2020/10/26 21:21
 */
public class StackSequences_946 {

    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int i = 0, j = 0;
        while (i < pushed.length || j < popped.length) {
            if (stack.isEmpty()) {
                stack.push(pushed[i++]);
            } else {
                while (i < pushed.length && !stack.isEmpty() && stack.peek() != popped[j]) {
                    stack.push(pushed[i++]);
                }
                if (stack.peek() != popped[j]) {
                    return false;
                } else {
                    stack.pop();
                    j++;
                }
            }
        }
        return true;
    }

}
